/**
 * 邻接矩阵图的拓扑排序
*/
#include "Queue.c"
#include "MGraph.c"

#ifndef MGRAPH_TOP_SORT
#define MGRAPH_TOP_SORT

// 建立，并初始化顶点入度数组
int* initIndegree(MGraph* graph) {
    // 使用 calloc 方法，会把内容初始化为 0
    int* indegree = (int*) calloc(graph->vertexNum, sizeof(int));
    /* 遍历图，得到indegree[] */
    for (int j=0; j < graph->vertexNum; j++) {
        // 第 j 个节点的入度，即与第 j 列连接的边数和
        for (int i=0; i < graph->vertexNum; i++) {
            if (isConnection(graph, i, j)) {
                indegree[j]++;
            }
        }
    }
    return indegree;
}

// 建立，并初始化顶点出度数组
int* initOutdegree(MGraph* graph) {
    int* outdegree = (int*) calloc(graph->vertexNum, sizeof(int));
    /* 遍历图，得到indegree[] */
    for (int i=0; i < graph->vertexNum; i++) {
        // 第 i 个节点的出度，即与第 i 行连接的边数和
        for (int j=0; j < graph->vertexNum; j++) {
            if (isConnection(graph, i, j)) {
                outdegree[i]++;
            }
        }
    }
    return outdegree;
}


WeightType max(WeightType w1, WeightType w2) {
    return w1 >= w2 ? w1 : w2;
}

WeightType min(WeightType w1, WeightType w2) {
    return w1 <= w2 ? w1 : w2;
}

int topSort(MGraph* graph, int topOrder[], int earliest[]) {
    /* 对Graph进行拓扑排序,  TopOrder[]顺序存储排序后的顶点下标 */
    int* indegree = initIndegree(graph);

    Queue* queue = createQueue();
    /* 将所有入度为0的顶点入列 */
    for (int i=0; i < graph->vertexNum; i++) {
        if (indegree[i] == 0) {
            enQueue(queue, i);
        }
        // 初始化 earliest
        earliest[i] = 0;
    }

    /* 下面进入拓扑排序 */ 
    int cnt = 0; 
    
    while (!isEmptyQueue(queue)) {
        /* 弹出一个入度为0的顶点 */
        int v = deQueue(queue); 
        topOrder[cnt++] = v; /* 将之存为结果序列的下一个元素 */
        
        /* 对V的每个邻接点W */
        for (int w=0; w < graph->vertexNum; w++) {
            // 计算 v 的 earliest
            // 这里 w 是 v 的前序节点
            if (isConnection(graph, w, v)) {
                // 有边<w, v>
                earliest[v] = max(earliest[v], earliest[w] + graph->g[w][v]);
            }
            // 这里  w 是 v 的后序节点
            if (isConnection(graph, v, w)) {
                // 有边<v, w>
                --indegree[w];
                /* 若删除V使得W入度为0 */
                if (indegree[w] == 0) {
                    /* 则该顶点入列 */
                    enQueue(queue, w);
                }
            }
        }
    }
    free(indegree);
    freeQueue(queue);
    return cnt == graph->vertexNum;
}

// 获取数组中的最大值
int findMax(int a[], int n) {
    int max = 0;
    for (int i=0; i<n; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    return max;
}


void calLatest(MGraph *graph, int latest[], int maxTime) {
    int* outdegree = initOutdegree(graph);

    Queue* queue = createQueue();
    /* 将所有出度为0的顶点入列 */
    for (int i=0; i < graph->vertexNum; i++) {
        if (outdegree[i] == 0) {
            enQueue(queue, i);
        }
        // 初始化 latest
        latest[i] = maxTime;
    }

    while (!isEmptyQueue(queue)) {
        /* 弹出一个出度为0的顶点 */
        int j = deQueue(queue); 

        /* 对 j 的每个前序邻接点 i */
        for (int i=0; i < graph->vertexNum; i++) {
            if (isConnection(graph, i, j)) {
                // 有边<i, j>
                latest[i] = min(latest[i], latest[j] - graph->g[i][j]);
                --outdegree[i];
                /* 若删除 j 使得 i 出度为0 */
                if (outdegree[i] == 0) {
                    /* 则该顶点入列 */
                    enQueue(queue, i);
                }
            }
        }
    }
    free(outdegree);
    freeQueue(queue);
}

// 计算关键路径，关键路径写入数组 path, 返回关键路径数量
int calImportantPath(MGraph *graph, int earliest[], int latest[], Edge path[]) {
    int cnt = 0;
    for (int i=0; i < graph->vertexNum; i++) {
        for (int j=0; j < graph->vertexNum; j++) {
            if (i!=j && latest[j] - earliest[i] - graph->g[i][j] == 0) {
                path[cnt++] = createEdge(i, j, graph->g[i][j]);
            }
        }
    }
    return cnt;
}

#endif
